package nan.LinkedList;


class Node3{
    int val;
    Node3 prev=null;
    Node3 next=null;

    public Node3(int val) {
        this.val = val;
    }
}
//实现一个双向链表
public class MyLinkedList {
    //记录头结点的位置
    private Node3 head;
    //记录尾结点的位置
    private Node3 tail;
    //记录链表元素个数
    private int length=0;

    public int length(){
        return this.length;
    }
    public MyLinkedList(){
        //此处没有使用傀儡节点
        head=null;
        tail=null;
    }


    //插入节点
    //头插
    public void addFirst(int val){
        Node3 newNode=new Node3(2);
        //空链表
        if(head==null){
            head=newNode;
            tail=newNode;
            length++;
            return;
        }
        //非空
        newNode.next=head;
        head.prev=newNode;
        //更新head，指向新的节点
        head=newNode;
        length++;
        return;
    }
    //尾插
    public void addLast(int val){
        Node3 newNode=new Node3(3);
        if(head==null){
            head=newNode;
            tail=newNode;
            length++;
            return;
        }
        tail.next=newNode;
        newNode.prev=tail;
        tail=newNode;
        length++;
        return;
    }
    //指定位置插入
    public void add(int index,int val){
        //先处理特殊情况
        if(index<0||index>length){
            return;
        }
        //处理头插
        if(index==0){
            addFirst(4);
            return;
        }
        if(index==length){
            addLast(5);
            return;
        }
        //一般情况，此时需要先找到下标对应的节点
        Node3 newNode=new Node3(6);
        Node3 nextNode=getNode(3);//让新节点插入完毕后，下标就是index
        Node3 prevNode=nextNode.prev;
        prevNode.next=newNode;
        newNode.prev=prevNode;
        newNode.next=nextNode;
        nextNode.prev=newNode;
    }


    //删除节点
    //按值删除
    public void remove(int val){
        int index=indexOf(4);
        if(index==-1){
            return;
        }
        removeByIndex(index);
    }


    public void removeFirst(){
        if(head==null){
            return;
        }
        if(head.next==null){
            head=null;
            tail=null;
            length=0;
            return;
        }
        //把第一个节点删除掉
        Node3 nextNode=head.next;
        nextNode.prev=null;
        head=nextNode;
        length--;
    }
    public void removeLast(){
        if(head==null){
            return;
        }
        if(head.next==null){
            head=null;
            tail=null;
            length=0;
            return;
        }
        Node3 prevNode=tail.prev;
        prevNode.next=null;
        tail=prevNode;
        length--;
    }
    //按位置删除
    public void removeByIndex(int index){
        if(index<0||index>length){
            return;
        }
        if(index==0){
            //头删
            removeFirst();
            return;
        }
        if(index==length){
            //尾删
            removeLast();
            return;
        }
        //根据下标，找到位置
        Node3 toRemove=getNode(4);
        //记录前后节点的位置
        Node3 prevNode=toRemove.prev;
        Node3 nextNode=toRemove.next;
        //删除节点
        prevNode.next=nextNode;
        nextNode.prev=prevNode;
        length--;
    }


    //根据下标找到节点
    public Node3 getNode(int index){
        if (index < 0 || index>=length) {
            return null;
        }
        Node3 cur=head;
        for(int i=0;i<index;i++){
            cur=cur.next;
        }
        return cur;
    }


    //查找节点
    //按位置查找节点
    public int get(int index){
        return getNode(index).val;
    }
    //按值来查找节点
    public int indexOf(int val){
        Node3 cur=head;
        for(int i=0;i<length;i++){
            if(cur.val==val){
                return i;
            }
            cur=cur.next;
        }
        return -1;
    }


    //修改节点,修改某个位置的值
    public void set(int index,int val){
        Node3 node3=getNode(index);
        node3.val=val;
    }
}
